161. One Edit Distance
Medium

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

  • Insert exactly one character into s to get t.
  • Delete exactly one character from s to get t.
  • Replace exactly one character of s with a different character to get t.

 

Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

Example 2:

Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.

Example 3:

Input: s = "a", t = ""
Output: true

Example 4:

Input: s = "", t = "A"
Output: true

 

Constraints:

  • 0 <= s.length <= 104
  • 0 <= t.length <= 104
  • s and t consist of lower-case letters, upper-case letters and/or digits.
Accepted
142.9K
Submissions
428.8K
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.56 (36 votes)

Premium

Solution


Approach 1: One pass algorithm

Intuition

First of all, let's ensure that the string lengths are not too far from each other. If the length difference is 2 or more characters, then s and t couldn't be one edit away strings.

compute

For the next let's assume that s is always shorter or the same length as t. If not, one could always call isOneEditDistance(t, s) to inverse the string order.

Now it's time to pass along the strings and to look for the first different character.

If there is no differences between the first len(s) characters, only two situations are possible :

  • The strings are equal.

  • The strings are one edit away distance.

compute

Now what if there is a different character so that s[i] != t[i].

  • If the strings are of the same length, all next characters should be equal to keep one edit away distance. To verify it, one has to compare the substrings of s and t both starting from the i + 1th character.

  • If t is one character longer than s, the additional character t[i] should be the only difference between both strings. To verify it, one has to compare a substring of s starting from the ith character and a substring of t starting from the i + 1th character.

compute

Implementation

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) in the worst case when string lengths are close enough abs(ns - nt) <= 1, where N is a number of characters in the longest string. O(1)\mathcal{O}(1) in the best case when abs(ns - nt) > 1.

  • Space complexity : O(N)\mathcal{O}(N) because strings are immutable in Python and Java and to create substring costs O(N)\mathcal{O}(N) space.

Problem generalization : Edit distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

Report Article Issue

Comments: 29
closewen's avatar
Read More

This solution is not O(1) memory, each s.substring will create a new string object.

47
Show 4 replies
Reply
Share
Report
trkx48's avatar
Read More

Logic is like this

  • Get the length of both s & t strings as l1 and l2
  • If they differ more than 1, they are more than one edit distance apart, so straight return false.
  • Have two pointers i and j, starting with 0th index in s & t strings respectively and loop until they are same.
  • Now we are at a point where both chars pointed by i and j are different or we reach end of both strings.
  • If we reach end of both strings, it means both strings are same, so straight return false as same strings cannot be one edit distance apart.
  • If l1 > l2, which means s is longer than t, so only deletion is possible. Ignore the current character s[i], and see if remaining of s[i+1, l1] matches with t[j, l2]. If matches they are one edit distance apart, else no.
  • If l1 < l2, which means s is shorter than t, so only insertion is possible. Assuming we insert t[j] at ith index in s and see if remaining of s[i, l1] matches with t[j+1, l2]. If matches they are one edit distance apart, else no.
  • If l1 == l2, which means s and t are of same length, so only replacing is possible. Assuming we replace s[i] with t[j] and see if remaining of s[i+1, l1] matches with t[j+1, l2]. If matches they are one edit distance apart, else no.
class Solution {
    public boolean isOneEditDistance(String s, String t) {
        
        int l1 = s.length();
        int l2 = t.length();
        
        if (Math.abs(l1 - l2) > 1) {
            // more than 1 edit distance apart
            return false;
        }
        
        int i = 0;
        int j = 0;
        
        while (i < l1 && j < l2 && s.charAt(i) == t.charAt(j)) {
            i++;
            j++;
        }
        
        if (i == l1 && j == l2) {
            return false;
        }
        
        if (l1 > l2) {
            // deletion is only possible
            return s.substring(i + 1).equals(t.substring(j));
        } else if (l1 < l2) {
            // insertion is only possible
            return s.substring(i).equals(t.substring(j + 1));
        } else {
            // replacing is only possible
            return s.substring(i + 1).equals(t.substring(j + 1));
        }
    }
}

20
Reply
Share
Report
milinthosani's avatar
Read More

My 2 pointer approach:
Time complexity: O(max(m,n))
Space complexity: O(1)

class Solution(object):
    def isOneEditDistance(self, s, t):
        if abs(len(s) - len(t)) > 1 or s == t:
            return False
        
        found_inequality = False
        i = j = 0
        
        while i < len(s) and j < len(t):
            if s[i] != t[j]:
                if found_inequality: return False
                found_inequality = True
                if len(s) < len(t): i -= 1
                elif len(s) > len(t): j -= 1
            i += 1
            j += 1
        
        return True

29
Show 3 replies
Reply
Share
Report
renjunyao's avatar
Read More

We can use two pointers, instead of substrings to make it O(1) space.

15
Reply
Share
Report
mn002's avatar
Read More

I would say that identical strings should return true. I hate it when these problems aren't fully specified.

6
Show 1 reply
Reply
Share
Report
beauji_1116's avatar
Read More

Why output should be false when input is "c" and "c"? It didn't say u cannot use the same character to replace the old one, so why i cannot use a letter "c" to replace itself?

5
Show 1 reply
Reply
Share
Report
Aj007's avatar
Read More

Correct me if I am wrong but since a substring is created in the approach 1, this algo is O(N) space too since in Java, C# strings are immutable.

2
Reply
Share
Report
ncoder11's avatar
Read More

A very straightforward and easy to understand solution, of course the code can be compressed by adding some better if..else, but it is still fairly fast.
Runtime: 1 ms, faster than 99.67% of Java online submissions for One Edit Distance.
Memory Usage: 38 MB, less than 85.29% of Java online submissions for One Edit Distance.

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int lenDiff = s.length() - t.length();
        if(lenDiff > 1 || lenDiff < -1)
        {
            return false;
        }

 
        int distance = 0;
        
        if(lenDiff == 1)    //removal case; s>t
        {
            if(t == null || t.isEmpty())
                return true;
            distance = s.length();
            int j = 0;
            for(int i=0; i<s.length(); i++)
            {
                if(s.charAt(i) == t.charAt(j))
                {
                    distance--;
                    j++;
                    if(j >= t.length())
                       break;
                }
            }
        }
        else if(lenDiff == -1)  //insertion case; t>s
        {
            if(s == null || s.isEmpty())
                return true;
            distance = t.length();
            int j = 0;
            for(int i=0; i<t.length(); i++)
            {
                if(t.charAt(i) == s.charAt(j))
                {
                    distance--;
                    j++;
                    if(j >= s.length())
                        break;
                }
            }
        }
        else if(lenDiff == 0) //replacement case; s==t
        {
            if(t == null || t.isEmpty())
                return false;
            distance=s.length();
            for(int i=0; i<s.length(); i++)
            {
              if(t.charAt(i) == s.charAt(i))
                distance--;
            }
        }
        
        if(distance == 1)
            return true;
        else
            return false;
    }
}

2
Show 1 reply
Reply
Share
Report
ssl_91's avatar
Read More

return true works fine for me. Curious to know when (ns + 1 == nt) will be executed?

In any, match or not-match case, it should be already returned in the for loop, AFAIK.

1
Show 3 replies
Reply
Share
Report
atulagrawal91's avatar
Read More

    if (Math.abs(s.length() - t.length()) > 1)
      return false;

    int countChanges = 0;
    char[] arr = s.toCharArray();
    for(int i = 0; i <  arr.length ; i++){
      if(arr[i] != t.charAt(i)){
        countChanges++;
      }
      if(countChanges > 1){
        break;
      }
    }

    if(countChanges <= 1){
      return true;
    }

    return false;
  } ```

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/07/2021 11:55Accepted8 ms6.7 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium